package com.clps.algorithm.chapter05.外星语言是否排序;

import java.util.List;

/**
 * 有一门外星语言，它的字母表刚好包含所有的英文小写字母，只是字母表的顺序不同。给定一组单词和字母表顺序，请判断这些单词是否按照字母表的顺序排序。
 * 例如，输入一组单词["offer", "is", "coming"]，以及字母表顺序"zyxwvutsrqponmlkjihgfedcba"，由于字母'o'在字母表中位于'i'的前面，所以单词"offer"排在"is"的前面；
 * 同样由于字母'i'在字母表中位于'c'的前面，所以单词"is"排在"coming"的前面。因此这一组单词是按照字母表顺序排序的，应该输出true。
 */
public class demo01 {

    public static void main(String[] args) {

    }

    public int findMinDifference(List<String> timePoints){
        if(timePoints.size()>1440){
            return 0;
        }

     Boolean minuteFlags[] = new Boolean[1440];
        for (String time : timePoints) {
            String t[] = time.split(":");
            int minute = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
            if(minuteFlags[minute]){
                return 0;
            }

            minuteFlags[minute] = true;
        }
        return  findMinDifference1(minuteFlags);
    }

    private int findMinDifference1(Boolean[] minuteFlags) {
        int minDiff01 = minuteFlags.length -1;
        int prev = -1;
        int first = minuteFlags.length -1;
        int laset = -1;
        for (int i = 0; i <minuteFlags.length ; i++) {
            if(minuteFlags[i]){
                if(prev>=0){
                    minDiff01 = Math.min(i-prev,minDiff01);
                }
                prev = i;
               first = Math.min(i,first);
               laset = Math.max(i,laset);
            }
        }

        minDiff01 = Math.min(first+minuteFlags.length- laset,minDiff01);
        return minDiff01;
    }
}
